class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        this.count=0;
        if(nums==null||nums.length<2){
            return 0;
        }
        process(nums,0,nums.length-1);
        return count;
    }

    private void process(int[] nums, int L, int R) {
        if(L>=R){
            return ;
        }
        int mid = L + ((R-L)>>1);
        process(nums,L,mid);
        process(nums,mid+1,R);
        merge(nums,L,mid,R);

    }

    private void merge(int[] arr, int L, int M,int R) {
        int[] help = new int[R-L+1];
        int i=0;
        int p1= L;
        int p2=M+1;
        while(p1<=M&&p2<=R){
//            res += arr[p1] > arr[p2] ? M-L+1 : 0 ;
//            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
            if(arr[p1]<=arr[p2]){
                help[i++]=arr[p1++];
            }else{
                count += M-p1+1;
                help[i++] = arr[p2++];
            }
        }
        while(p1<=M){
            help[i++]=arr[p1++];
        }
        while(p2<=R){
            help[i++]=arr[p2++];
        }
        for(int j=0 ; j <help.length;j++){
            arr[L+j]=help[j];
        }


    }
}